#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    struct Node
    {
        int val;
        ListNode* ptr;
        bool operator <(const Node& a)const
        {
            return val > a.val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<Node> pq;
        for (auto it : lists)
            if (it) pq.push({ it->val,it });

        ListNode guard, * tail = &guard;
        while (pq.size())
        {
            auto t = pq.top();
            pq.pop();
            tail->next = t.ptr;
            tail = tail->next;
            if (t.ptr->next) pq.push({ t.ptr->next->val,t.ptr->next });
        }
        return guard.next;
    }
};